Augmenting Path

定义 Definition

Augmenting path（增广路）：在网络流或二分图匹配中，一条相对于当前解仍“可改进”的路径。沿该路径进行增广（对边的流量/匹配状态做相应调整）可以使总流量增加，或使匹配规模增大。常见于 Ford–Fulkerson 最大流算法与 Hopcroft–Karp 最大匹配算法等。（在不同问题里，路径的具体形式略有差异。）

发音 Pronunciation

/ɔːɡˈmentɪŋ pæθ/

例句 Examples

We found an augmenting path and increased the matching by one.
我们找到了一个增广路，使匹配数量增加了 1。

After each BFS level graph is built, the algorithm searches for multiple augmenting paths to speed up the maximum matching.
在构建好每一轮 BFS 的分层图之后，算法会寻找多条增广路来加速求最大匹配。

词源 Etymology

augmenting 来自 augment，意为“增加、扩充”（源于拉丁语 augmentare，与“增长”相关）；path 意为“路径”。合起来就是“用来增加（流量/匹配）的路径”，因此译作“增广路”。

相关词 Related Words

• Augment
• Residual Graph
• Residual Capacity
• Flow Network
• Maximum Flow
• Matching
• Bipartite Graph
• Ford–Fulkerson
• Edmonds–Karp
• Hopcroft–Karp

文学作品/经典出处 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：在最大流与二分图匹配相关章节中使用并讲解 augmenting path。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：系统讨论残量网络与 augmenting paths 在网络流算法中的作用。
• “An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs”（Hopcroft & Karp, 1973）：提出通过寻找多条增广路加速二分图最大匹配的经典方法。